Schönen guten Tag, Strichabend. Der Juli hat sich schon auf dem Weg zum Berch, so ist das hier.

So, die ersten Flüchtübungen sind teilweise schon korrigiert. Teil ist, glaube ich,

man noch dabei. Wer von Ihnen hat in die Korrektur schon bekommen? Wer von Ihnen ist zufrieden?

Und wer ist unzufrieden? Jetzt hätte ich mir die Arme merken müssen. Keiner.

Okay, super. Spann, wie es war, da geht. Kleiner Hinweis zu den Lösungen, die Sie einreichen. Sie

würden uns einen großen Gefallen tun, wenn man die lesen könnte. Also einige sind ehrlich gesagt

so aus, von geschmiert. Da konnten wir, könnten wir es beim Bestmüll nicht lesen. Und noch ein

anderer Hinweis, Kaffee Flecken auf den Lösungen, die man einreicht, fördern auch nicht die

Lesbarkeit ihre eingereichten Lösungen. Es ist kein Witz, es ist teilweise aus. Ich weiß nicht,

ob die kurz vorgemacht wurden. Wie gesagt, was wir nicht lesen können und wir geben uns müde

Sachen zu lesen, können wir leider auch nicht bewerten zu es das Nummerin. Okay, aber zwischen mir und

dem Berch wahrscheinlich, zwischen uns und dem Berch steht noch ein ganz spannendes Thema. Wir haben

quasi den Jackport heute. Wir sind fast beim Sortieren zu Ende. Wir gucken uns nochmal an,

womit wir beim letzten Mal aufgehört haben. Beim letzten Mal haben wir uns mit Merch-Sort beschäftigt.

Und das cooler Merch-Sort war, dass der eine Komplexität von N-Log N hat. Und die Idee war

am Wesentlichen, dass wir anfangen, die Menge rikosiv aufteilen und dann jeweils die richtigen

Teilergebnisse zusammenmischen. Und das machen wir indem wir ein bisschen Speicher zusätzlich benutzen.

Jetzt wollen wir uns heute in der Vorlesung mit dem wunderschönen Kriksort beschäftigen.

Also das ist quasi heute Teil der Vorlesung, Kriksort. Und die Frage ist natürlich,

wenn wir jetzt schon einfach fahren haben, was die Loerbauen trifft. Also wir wissen, wir können

nicht besser sein durch Vergleichsbasite zu sortieren. Jetzt haben wir im Beispiel, dass die

Loerbauen quasi erfüllt. Ja, warum gucken wir uns denn noch Kriksort an? Einfach, weil wir nichts

besseres vor haben oder was, warum gucken wir uns Kriksort an? Das ist eine Idee. Was könnte uns

an Möchstort einfach nicht gefallen? Ja, genau. Also der Möchstort, der Möchstort hat ein Speicherkomplexität

von O von N. Das heißt, damit er so sortieren kann, braucht zusätzlichen Speicher und dann stellt

sich natürlich die Frage, können wir diese Baunen nur erreichen, weil wir den zusätzlichen Speicher

haben oder schaffen wir es auch in Plays, also ohne den zusätzlichen Speicher. So, dann wird mich

auch noch interessieren, bevor wir loslegen. Wir haben ja in der Woche wie angekündigt die

Berufungsvorträge, vier von denen waren schon durch. Ich habe gesehen einige von ihnen waren auch in

den Summräum drin. Die letzte Gelegenheit bietet sich quasi morgen früh um 8. Also wenn sie vom

Bercht zurückkommen, können sie quasi kurz den Rechner einschalten und ich weiß gar nicht, ob das

lange aufhat. Wie dir auch sei, also die erste Veranstaltung fängt um 8 Uhr an, sollte das zeitlich ein

bisschen eng werden, haben sie noch die zweite Möglichkeit, ich glaube um 12 Uhr. Wie gesagt, es wäre gut,

wenn wir da auch ein bisschen Feedback kriegen, damit wir verstehen, ob das verständlich war,

was sie gemacht haben oder nicht. Besetzt haben die Kandidaten, die fast vor jeder

Transformation sehr unterschiedlich vorgestellt. Also es gab genau, ich würde sagen, kein Vollesungsbeispiel.

Ich glaube 20 Minuten, die hatten alle, also die hatten alle den einrecht kurzen Zeitraum.

Ja, die waren teilweise sehr unterschiedlich. Also einige, eine hat es sehr visuell gemacht,

da wird etwas eigentlich sehr schön zu sehen, was bei Fouille passiert, aber es war nicht ganz klar,

als ich glaube im Flementieren hätte, dass keiner von ihnen gekonnt danach. Andere haben es auf den

Formel gemacht, die erste hat sehr ergebrasch gemacht, also viele unterschiedliche Zugänge zum

gleichen Thema. Sehr spannend. Okay, dann legen wir los. Also heute ist unser Thema QuickSort und

QuickSort ist natürlich auch ein Algorithmus, der dem Prinzip Teile und Tersche folgt. Also hier wir folgen

auch den bekannten Teile und Tersche-Prinzip oder die weiterten Konkarn. Jetzt schon ein paar Teile

und Tersche. Und die Idee ist, wie immer, wir teilen die Menge auf in Teilprobleme, die ungefähr

die gleiche Struktur haben, sodass wir den gleichen Algorithmus auf Teilprobleme anmenden können,

das auf Teilen der folgt im Wesentlichen so weit, bis wir eine Menge haben, mit der wir umgehen

können. Und das tolle, das tolle im Wesentlichen an dem QuickSort ist, das Ganze sortieren,

in Place funktioniert. Was wir machen, wir werden im Prinzip das Array, wie gesagt, in Placeort

hier, das heißt, wir haben keinen signifikanten weiteren Speicher und dafür führen wir folgende Notation